#include <algorithm>
#include <vector>
#include <stdio.h>


/*
 *方法二:二进制组合算法:
 *思路是开一个数组，其下标表示1到m个数，数组元素的 为1表示其下标
 *代表的数被选中，为0则没选中。    
 *首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。    
 *然后从左到右扫描数组元素
 *的"10"组合，找到第一个"10"组合后将其变为"01"组合，
 *同时将其左边的所有"1"全部移动到数组的最左端(只有第一位变为0才需要移动，
 *否则其左边的1本来就在最左端，无需移动)。    
 *当第一个"1"移动到数组的m-n的位置，
 *即n个"1"全部移动到最右端时，就得到了最后一个组合。 
 */

void print(const std::vector<char>& flags)
{
    std::vector<char>::const_iterator iter = flags.begin();
    for (;iter != flags.end(); ++iter) {
        fprintf(stdout, "%d ", *iter);
    }
    fprintf(stdout, "\n");
}

void select(std::vector<char>& flags)
{
    for (size_t len = 1; len <= flags.size(); ++len) {
        std::fill(flags.begin(), flags.begin() + len, 1); 
        std::fill(flags.begin() + len, flags.end(), 0); 
        bool has10 = false;
        do {
            print(flags);
            has10 = false;
            for (size_t j = 0; j < flags.size() - 1; j++) {
                if (flags[j]  && !flags[j + 1]) {
                    has10 = true;
                    flags[j] = 0;
                    flags[j + 1] = 1;
                    if (flags[0] == 0) {
                        for (int m = 0, n = 0; m < j; m++) {
                            if (flags[m]) {
                                flags[m] = 0;
                                flags[n] = 1;
                                n++;
                            }
                        }
                    }
                    break;
                }
            }
        } while (has10);
    }
}

void combination(int* arr, size_t arr_len, int need_num, int* out, size_t out_len) {

    // 出口 已经满足选取个数
    if (need_num == 0) {
        for (size_t i = 0; i < out_len; i++) {
            fprintf(stdout, "%d ", out[i]); 
        }
        fprintf(stdout, "\n"); 
        return;
    }

    //从后往前依次选定一个
    for (size_t i = arr_len; i >= need_num; --i) {
        out[need_num - 1] = arr[i - 1]; //选定一个后
        combination(arr, i - 1, need_num - 1,  out, out_len); // 从前i-1个里面选取m-1个进行递归
    }
}

void select2() {
    int arr[] = {1, 2, 3, 4, 5};
    int out[] = {0, 0, 0, 0, 0};
    size_t len = sizeof(arr) / sizeof(arr[0]);
    size_t select = 3;
    combination(arr, len, select, out, select);
}

int main ()
{
    //std::vector<char> flags;
    //flags.resize(5);
    //select(flags);
    select2();
    return 0;
}
